package dp;

import java.util.Arrays;
import java.util.Comparator;

/**
 * Dynamic Programming implementation of Box Stacking problem
 * 
 * Adapted from http://www.geeksforgeeks.org/dynamic-programming-set-21-box-stacking-problem/
 * 
 * Time Complexity: O(n^2)
 * Auxiliary Space: O(n)
 * */
public class BoxStacking {

	/**
	 * Returns the height of the tallest stack that can be formed with given type of boxes
	 * 
	 * @param  given boxes
	 * @param  number of boxes
	 * */
	public static int maxHeight(Box[] boxes){
		
		int numBoxes = boxes.length; // total number of boxes
		
		/**
		 * Create an array of all rotations of given boxes
		 * For example, for a box {1, 2, 3}, we consider three
		 * instances{{1, 2, 3}, {2, 1, 3}, {3, 1, 2}}
		 * */
		Box[] allPosibleRotations = new Box[3*numBoxes];
		int index = 0;
		for(int i = 0; i < numBoxes; i++){
			
			// copy the original box 
			allPosibleRotations[index++] = boxes[i];
			
			// first rotation of box
			int h1 = boxes[i].w;
			int w1 = boxes[i].h > boxes[i].d ? boxes[i].d : boxes[i].h;
			int d1 = boxes[i].h > boxes[i].d ? boxes[i].h : boxes[i].d;
			allPosibleRotations[index++] = new Box(h1, w1, d1);
			
			// second rotation of box
			int h2 = boxes[i].d;
			int w2 = boxes[i].h > boxes[i].w ? boxes[i].w : boxes[i].h;
			int d2 = boxes[i].h > boxes[i].w ? boxes[i].h : boxes[i].w;
			allPosibleRotations[index++] = new Box(h2, w2, d2);
		}

		
		// sort the allPosibleRotations array in decreasing order of base (w * d)
		Arrays.sort(allPosibleRotations, new BoxComparator());
		
		// print the sorted boxes
		for(Box box: allPosibleRotations){
			System.out.print(box + " ");
		}
		System.out.println();
		
		// current number of boxes
		numBoxes *= 3;
		
		// msh[i] is Maximum possible Stack Height with box i on top
		int[] msh = new int[numBoxes];
		
		// worst case - hight of each box
		for(int i = 0; i < numBoxes; i++){
			msh[i] = allPosibleRotations[i].h;
		}
		
		// variable to hold msh
		int maxHeight = -1;
	
		// same as LIS
		for(int i = 1; i < numBoxes; i++){
			for(int j = 0; j < i; j++){
				if(allPosibleRotations[i].w < allPosibleRotations[j].w 
						&& allPosibleRotations[i].d < allPosibleRotations[j].d 
						&& msh[i] < msh[j] + allPosibleRotations[i].h){
					msh[i] = msh[j] + allPosibleRotations[i].h;
					
					// maintain current msh
					if(maxHeight < msh[i]){
						maxHeight = msh[i];
					}
				}
			}
		}
		
		return maxHeight; // max height of stack
	}
	
	
	// Box class
	private static class Box{
		// height, width and depth of the box
		int h, w, d; // by convention w <= d
		
		Box(int h, int w, int d){
			this.h = h; 
			this.w = w < d ? w : d;  // for convention maintain w <= d
			this.d = w < d ? d : w;
		}
		
		@Override
		public String toString(){
			return "{"+h+","+w+","+d+"}";
		}
	}
	
	
	// comapartor to sort boxes in decreasing order of base (w * d)
	private static class BoxComparator implements Comparator<Box>{
		public int compare(Box box1, Box box2){
			return box2.w * box2.d - box1.w * box1.d; 
		}
	}
	
	
	// test
	public static void main(String[] args){
		// test 1
		Box[] boxArray1 = {new Box(4, 6, 7), new Box(1, 2, 3), new Box(4, 5, 6), new Box(10, 12, 32)};
		System.out.println(maxHeight(boxArray1)); // ans is 60
		
		// test 2
		Box[] boxArray2 = {new Box(5, 2, 4), new Box(1, 2, 4), new Box(4, 2, 4)};
		System.out.println(maxHeight(boxArray2)); // ans is 11
		
	}
}
